Michał Franciszek Goleniewski sinh ngày 16 tháng 8 năm 1922 tại thành phố Nesvizh, thủ phủ huyện Nesvizh, tỉnh Nowogródek Đệ Nhị Cộng hòa Ba Lan (nay là phủ huyện Niasviž, tỉnh Minsk, Belarus).[1] Cha là Michał (29 tháng 9 năm 1883 - 17 tháng 5 năm 1952) xuất thân từ miền biên viễn Vương quốc Ba Lan, làm nghề kế toán, sau chiến tranh thì điều hành một nhà máy chưng cất rượu;[2] mộ phần nằm ở Wolsztyn (trên bia mộ ghi sai năm sinh là 1893).[3] Mẹ là Janina[4] nhũ danh Turynskaya.[1] Ông nội tên là Antoni còn bà nội là Marcela (nhũ danh Buczynska hoặc Byezinska).[3] Lúc nhỏ, gia đình chuyển đến thị trấn Ciosaniec gần Wolsztyn.[5] Tại đó, Michał học phổ thông (một số nguồn ghi chỉ hết lớp 4 bổ túc)[2] và tốt nghiệp trung học.[6] Khi bị CIA thẩm vấn, Goleniewski cố tình đưa thông tin sai lệch rằng đã học ba năm tại Khoa Luật Đại học Poznań, rồi chuyển đến Warszawa và tốt nghiệp thạc sĩ Đại học Warszawa năm 1956. Văn thư lưu trữ các trường đại học này đều không có thông tin quá trình Goleniewski theo học,[7] có thể ông nói dối vì muốn được nhập tịch nhanh chóng.[8]

Thời Đức chiếm đóng Ba Lan, Goleniewski làm người đưa tin[6] và kế toán cho văn phòng "Reichsland"[lower-alpha 1] của Đức quản lý đất đai tịch thu từ người Ba Lan.[9] Ông thông thạo tiếng Đức, thậm chí có thể nói một số phương ngữ Đức nên được Reichsland tuyển dụng. Những hoạt động thời chiến của Goleniewski không được nghiên cứu chi tiết đầy đủ.[10] Michał khai rằng từng bị Đức bắt giữ và buộc tội tham gia tổ chức ngầm chống phát xít.[5][11] Cuối năm 1944, ông bị ốm nặng và đang nằm viện khi Hồng quân tiến vào Wolsztyn.[6] Cuối thập niên 1940 có một vụ điều tra hình sự nhằm làm sáng tỏ nghi ngờ Michał cộng tác với Đức quốc xã thời làm cho Reichsland nhưng các cáo buộc đã không được xác nhận.[12]

Sĩ quan tình báo Bộ Nội vụ PPR Đại tá Henryk Bosak nói Michał tham gia Hồng quân và được đi học trường của NKVD tại Kuibyshev năm 1944, rồi đặc phái cử về Tổng cục Thông tin Quân đội Ba Lan.[13] Trưởng tình báo Ba Lan 2002-2004 Zbigniew Siemiątkowski cũng nhắc đến chuyện Goleniewski có mối liên hệ với NKVD. Tuy nhiên không tìm thấy tư liệu nào chứng thực các việc này.[14]